//给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1]
// 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘
//积是18。 
//
// 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 
//
// 
//
// 示例 1： 
//
// 输入: 2
//输出: 1
//解释: 2 = 1 + 1, 1 × 1 = 1 
//
// 示例 2: 
//
// 输入: 10
//输出: 36
//解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36 
//
// 
//
// 提示： 
//
// 
// 2 <= n <= 1000 
// 
//
// 注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/ 
// Related Topics 数学 动态规划 👍 189 👎 0


package leetcode.editor.cn;

//Java：剪绳子 II
public class JianShengZiIiLcof {
    public static void main(String[] args) {
        Solution solution = new JianShengZiIiLcof().new Solution();
        // TO TEST
        System.out.println(solution.cuttingRope(10));
        System.out.println(solution.cuttingRope(5));
        System.out.println(solution.cuttingRope(8));
        System.out.println(solution.cuttingRope(4));
        System.out.println(solution.cuttingRope(120));
        System.out.println(solution.cuttingRope(127));
        System.out.println(solution.cuttingRope(100));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int cuttingRope(int n) {
            if (n <= 3) return n - 1;
            int b = n % 3, p = 1000000007;
            long rem = 1, x = 3;
            for (int i = n / 3 - 1; i > 0; i = i / 2) {
                if (i % 2 == 1) rem = rem * x % p;
                x = x * x % p;
            }
            if (b == 0) return (int) (rem * 3 % p);
            if (b == 1) return (int) (rem * 4 % p);
            return (int) (rem * 6 % p);
        }

//        public int cuttingRope(int n) {
//            if (n <= 3) return n - 1;
//            long[] df = new long[n + 1];
//            df[0] = df[1] = 0;
//            df[2] = 1;
//            df[3] = 2;
//            // 973568760
//            int p = 1000000007;
//            for (int i = 4; i < df.length; i++) {
//                for (int j = 1; j < i; j++) {
//                    // 减去长度为j，剩下的i - j   j * df[i-j], j * (i - j)
//                    long a = df[j];
//                    long b = df[i - j];
//                    if (j == 1) a = 1;
//                    if (j == 2) a = 2;
//                    if (j == 3) a = 3;
//                    if ((i - j) == 1) b = 1;
//                    if ((i - j) == 2) b = 2;
//                    if ((i - j) == 3) b = 3;
//                    // 此方法只适用于 n值不大的时候
//                    df[i] = Math.max(df[i], a * b % p);
//                }
//            }
//            return (int) df[n];
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
